package leetcode.editor.cn;

import java.util.*;

class SubsetsIi {
    public static void main(String[] args) {
        Solution solution = new SubsetsIi().new Solution();
        solution.subsetsWithDup(new int[]{1, 2, 2});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*public List<List<Integer>> subsetsWithDup(int[] nums) {
            if (nums.length == 0) {
                return res;
            }
            Arrays.sort(nums);  // 必须要进行排序，才能达到去重效果
            backtracking(nums, 0, new boolean[nums.length]);
            return res;
        }

        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();

        public void backtracking(int[] nums, int startIndex, boolean[] used) {
            res.add(new ArrayList<>(path));
            if (startIndex >= nums.length) {
                return;
            }

            for (int i = startIndex; i < nums.length; i++) {
                if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {   // 已经被选择
                    continue;
                } else { // 注意不能放在if里面，以为if里面将 i > 0 之后才会进行判断
                    path.add(nums[i]);
                    used[i] = true;
                    backtracking(nums, i + 1, used);
                    used[i] = false;
                    path.removeLast();
                }
            }
        }*/

        public List<List<Integer>> subsetsWithDup(int[] nums) {
            Arrays.sort(nums);
            backtracking(nums, new boolean[nums.length], 0);
            // set做法
            // backtracking(nums, 0);
            return res;
        }

        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();

        public void backtracking(int[] nums, boolean[] used, int startIndex) {
            res.add(new ArrayList<>(path));
            if (startIndex >= nums.length) {
                return;
            }

            for (int i = startIndex; i < nums.length; i++) {
                if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;
                path.add(nums[i]);
                used[i] = true;
                backtracking(nums, used, i + 1);
                used[i] = false;
                path.removeLast();
            }
        }

        /**
         * 使用set
         *
         * @param nums
         * @param startIndex
         */
        /*public void backtracking(int[] nums, int startIndex) {
            res.add(new ArrayList<>(path));
            if (startIndex >= nums.length) {
                return;
            }

            Set<Integer> set = new HashSet<>();
            for (int i = startIndex; i < nums.length; i++) {
                if (!set.isEmpty() && set.contains(nums[i])) continue;
                set.add(nums[i]);
                path.add(nums[i]);
                backtracking(nums, i + 1);
                path.removeLast();
            }
        }*/

    }
//leetcode submit region end(Prohibit modification and deletion)

}
